package BlackRedTree;

public class BRTree {
    public static class TreeNode{
        public Integer val;
        public Color color;
        public TreeNode parent;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(Integer val) {
            this.val = val;
            //节点默认是红色
            this.color = Color.Red;
        }
    }
    //根节点
    public TreeNode root;

    //插入
    public void insert(int val) {
        TreeNode node = new TreeNode(val);
        if (root == null) {
            root = node;
            root.color = Color.Black;
            return;
        }
        //先将节点插入红黑树
        TreeNode tmp = root;
        TreeNode tParent = tmp.parent;
        while (tmp != null) {
            if (tmp.val < val) {
                tParent = tmp;
                tmp = tmp.right;
            } else if (tmp.val == val) {
                return;
            } else {
                tParent = tmp;
                tmp = tmp.left;
            }
        }
        //插入新节点
        if (tParent.val < val) {
            tParent.right = node;
        } else {
            tParent.left =  node;
        }
        node.parent = tParent;
        if (tParent.color == Color.Black) {
            return;
        }
        //调整节点
        TreeNode cur = node;
        TreeNode curParent = node.parent;
        TreeNode curPParent = curParent.parent;
        while(curParent != null && curParent.color == Color.Red) {
            curPParent = curParent.parent;
            if (curPParent.right != curParent) {
                //右子树存在且为红
                if (curPParent.right != null && curPParent.right.color == Color.Red) {
                    curParent.color = Color.Black;
                    curPParent.color = Color.Red;
                    curPParent.right.color = Color.Black;
                    cur = curPParent;
                } else {
                    if (cur == curParent.left) {
                        //右旋
                        turnR(curParent, curPParent);
                    } else {
                        //左旋
                        turnL(cur, curParent);
                        TreeNode t = cur;
                        cur = curParent;
                        curParent = t;
                        //右旋
                        turnR(curParent, curPParent);
                    }
                    if (curPParent == root) {
                        root = curParent;
                    }
                    break;
                }
            } else {
                //左子树存在且为红
                if (curPParent.left != null && curPParent.left.color == Color.Red) {
                    curParent.color = Color.Black;
                    curPParent.color = Color.Red;
                    curPParent.left.color = Color.Black;
                    cur = curPParent;
                } else {
                    if (cur == curParent.right) {
                        //左旋
                        turnL(curParent, curPParent);
                    } else {
                        //右旋
                        turnR(cur, curParent);
                        TreeNode t = cur;
                        cur = curParent;
                        curParent = t;
                        //左旋
                        turnL(curParent, curPParent);
                    }
                    if (curPParent == root) {
                        root = curParent;
                    }
                    break;
                }
            }
            curParent = cur.parent;
        }
        root.color = Color.Black;
    }
    //右旋
    public void turnR(TreeNode p, TreeNode pp) {
        pp.left = p.right;
        p.right = pp;
        p.parent = pp.parent;
        pp.left.parent = pp;
        pp.parent = p;
        p.color = Color.Black;
        pp.color = Color.Red;
        if (p.parent != null) {
            if (p.parent.left == pp) {
                p.parent.left = p;
            } else {
                p.parent.right = p;
            }
        }
    }
    //左旋
    public void turnL(TreeNode p, TreeNode pp) {
        pp.right = p.left;
        p.left = pp;
        pp.right.parent = pp;
        p.parent = pp.parent;
        pp.parent = p;
        p.color = Color.Black;
        pp.color = Color.Red;
        if (p.parent != null) {
            if (p.parent.left == pp) {
                p.parent.left = p;
            } else {
                p.parent.right = p;
            }
        }
    }
}
